/* -------------------------------------------------------------------------------

This code is based on source provided under the terms of the Id Software 
LIMITED USE SOFTWARE LICENSE AGREEMENT, a copy of which is included with the
GtkRadiant sources (see LICENSE_ID). If you did not receive a copy of 
LICENSE_ID, please contact Id Software immediately at info@idsoftware.com.

All changes and additions to the original source which have been developed by
other contributors (see CONTRIBUTORS) are provided under the terms of the
license the contributors choose (see LICENSE), to the extent permitted by the
LICENSE_ID. If you did not receive a copy of the contributor license,
please contact the GtkRadiant maintainers at info@gtkradiant.com immediately.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS IS''
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY
DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

----------------------------------------------------------------------------------

This code has been altered significantly from its original form, to support
several games based on the Quake III Arena engine, in the form of "Q3Map2."

------------------------------------------------------------------------------- */



/* marker */
#define MESH_C



/* dependencies */
#include "q3map2.h"



/*
LerpDrawVert()
returns an 50/50 interpolated vert
*/

void LerpDrawVert( bspDrawVert_t *a, bspDrawVert_t *b, bspDrawVert_t *out )
{
	int		k;
	
	
	out->xyz[ 0 ] = 0.5 * (a->xyz[ 0 ] + b->xyz[ 0 ]);
	out->xyz[ 1 ] = 0.5 * (a->xyz[ 1 ] + b->xyz[ 1 ]);
	out->xyz[ 2 ] = 0.5 * (a->xyz[ 2 ] + b->xyz[ 2 ]);

	out->st[ 0 ] = 0.5 * (a->st[ 0 ] + b->st[ 0 ]);
	out->st[ 1 ] = 0.5 * (a->st[ 1 ] + b->st[ 1 ]);
	
	for( k = 0; k < MAX_LIGHTMAPS; k++ )
	{
		out->lightmap[ k ][ 0 ] = 0.5f * (a->lightmap[ k ][ 0 ] + b->lightmap[ k ][ 0 ]);
		out->lightmap[ k ][ 1 ] = 0.5f * (a->lightmap[ k ][ 1 ] + b->lightmap[ k ][ 1 ]);
		out->color[ k ][ 0 ] = (a->color[ k ][ 0 ] + b->color[ k ][ 0 ]) >> 1;
		out->color[ k ][ 1 ] = (a->color[ k ][ 1 ] + b->color[ k ][ 1 ]) >> 1;
		out->color[ k ][ 2 ] = (a->color[ k ][ 2 ] + b->color[ k ][ 2 ]) >> 1;
		out->color[ k ][ 3 ] = (a->color[ k ][ 3 ] + b->color[ k ][ 3 ]) >> 1;
	}
	
	/* ydnar: added normal interpolation */
	out->normal[ 0 ] = 0.5f * (a->normal[ 0 ] + b->normal[ 0 ]);
	out->normal[ 1 ] = 0.5f * (a->normal[ 1 ] + b->normal[ 1 ]);
	out->normal[ 2 ] = 0.5f * (a->normal[ 2 ] + b->normal[ 2 ]);
	
	/* if the interpolant created a bogus normal, just copy the normal from a */
	if( VectorNormalize( out->normal, out->normal ) == 0 )
		VectorCopy( a->normal, out->normal );
}



/*
LerpDrawVertAmount()
returns a biased interpolated vert
*/

void LerpDrawVertAmount( bspDrawVert_t *a, bspDrawVert_t *b, float amount, bspDrawVert_t *out )
{
	int		k;
	
	
	out->xyz[ 0 ] = a->xyz[ 0 ] + amount * (b->xyz[ 0 ] - a->xyz[ 0 ]);
	out->xyz[ 1 ] = a->xyz[ 1 ] + amount * (b->xyz[ 1 ] - a->xyz[ 1 ]);
	out->xyz[ 2 ] = a->xyz[ 2 ] + amount * (b->xyz[ 2 ] - a->xyz[ 2 ]);
	
	out->st[ 0 ] = a->st[ 0 ] + amount * (b->st[ 0 ] - a->st[ 0 ]);
	out->st[ 1 ] = a->st[ 1 ] + amount * (b->st[ 1 ] - a->st[ 1 ]);
	
	for( k = 0; k < MAX_LIGHTMAPS; k++ )
	{
		out->lightmap[ k ][ 0 ] = a->lightmap[ k ][ 0 ] + amount * (b->lightmap[ k ][ 0 ] - a->lightmap[ k ][ 0 ]);
		out->lightmap[ k ][ 1 ] = a->lightmap[ k ][ 1 ] + amount * (b->lightmap[ k ][ 1 ] - a->lightmap[ k ][ 1 ]);
		out->color[ k ][ 0 ] = a->color[ k ][ 0 ] + amount * (b->color[ k ][ 0 ] - a->color[ k ][ 0 ]);
		out->color[ k ][ 1 ] = a->color[ k ][ 1 ] + amount * (b->color[ k ][ 1 ] - a->color[ k ][ 1 ]);
		out->color[ k ][ 2 ] = a->color[ k ][ 2 ] + amount * (b->color[ k ][ 2 ] - a->color[ k ][ 2 ]);
		out->color[ k ][ 3 ] = a->color[ k ][ 3 ] + amount * (b->color[ k ][ 3 ] - a->color[ k ][ 3 ]);
	}

	out->normal[ 0 ] = a->normal[ 0 ] + amount * (b->normal[ 0 ] - a->normal[ 0 ]);
	out->normal[ 1 ] = a->normal[ 1 ] + amount * (b->normal[ 1 ] - a->normal[ 1 ]);
	out->normal[ 2 ] = a->normal[ 2 ] + amount * (b->normal[ 2 ] - a->normal[ 2 ]);
	
	/* if the interpolant created a bogus normal, just copy the normal from a */
	if( VectorNormalize( out->normal, out->normal ) == 0 )
		VectorCopy( a->normal, out->normal );
}


void FreeMesh( mesh_t *m ) {
	free( m->verts );
	free( m );
}

void PrintMesh( mesh_t *m ) {
	int		i, j;

	for ( i = 0 ; i < m->height ; i++ ) {
		for ( j = 0 ; j < m->width ; j++ ) {
			Sys_Printf("(%5.2f %5.2f %5.2f) "
				, m->verts[i*m->width+j].xyz[0]
				, m->verts[i*m->width+j].xyz[1]
				, m->verts[i*m->width+j].xyz[2] );
		}
		Sys_Printf("\n");
	}
}


mesh_t *CopyMesh( mesh_t *mesh ) {
	mesh_t	*out;
	int		size;

	out = safe_malloc( sizeof( *out ) );
	out->width = mesh->width;
	out->height = mesh->height;

	size = out->width * out->height * sizeof( *out->verts );
	out->verts = safe_malloc( size );
	memcpy( out->verts, mesh->verts, size );

	return out;
}


/*
TransposeMesh()
returns a transposed copy of the mesh, freeing the original
*/

mesh_t *TransposeMesh( mesh_t *in ) {
	int			w, h;
	mesh_t		*out;

	out = safe_malloc( sizeof( *out ) );
	out->width = in->height;
	out->height = in->width;
	out->verts = safe_malloc( out->width * out->height * sizeof( bspDrawVert_t ) );

	for ( h = 0 ; h < in->height ; h++ ) {
		for ( w = 0 ; w < in->width ; w++ ) {
			out->verts[ w * in->height + h ] = in->verts[ h * in->width + w ];
		}
	}

	FreeMesh( in );

	return out;
}

void InvertMesh( mesh_t *in ) {
	int			w, h;
	bspDrawVert_t	temp;

	for ( h = 0 ; h < in->height ; h++ ) {
		for ( w = 0 ; w < in->width / 2 ; w++ ) {
			temp = in->verts[ h * in->width + w ];
			in->verts[ h * in->width + w ] = in->verts[ h * in->width + in->width - 1 - w ];
			in->verts[ h * in->width + in->width - 1 - w ] = temp;
		}
	}
}

/*
=================
MakeMeshNormals

=================
*/
void MakeMeshNormals( mesh_t in )
{
	int		i, j, k, dist;
	vec3_t	normal;
	vec3_t	sum;
	int		count;
	vec3_t	base;
	vec3_t	delta;
	int		x, y;
	bspDrawVert_t	*dv;
	vec3_t		around[8], temp;
	qboolean	good[8];
	qboolean	wrapWidth, wrapHeight;
	float		len;
	int				neighbors[8][2] =
					{
						{0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1}
					};
	
	
	wrapWidth = qfalse;
	for ( i = 0 ; i < in.height ; i++ ) {
		VectorSubtract( in.verts[i*in.width].xyz, 
			in.verts[i*in.width+in.width-1].xyz, delta );
		len = VectorLength( delta );
		if ( len > 1.0 ) {
			break;
		}
	}
	if ( i == in.height ) {
		wrapWidth = qtrue;
	}

	wrapHeight = qfalse;
	for ( i = 0 ; i < in.width ; i++ ) {
		VectorSubtract( in.verts[i].xyz, 
			in.verts[i + (in.height-1)*in.width].xyz, delta );
		len = VectorLength( delta );
		if ( len > 1.0 ) {
			break;
		}
	}
	if ( i == in.width) {
		wrapHeight = qtrue;
	}


	for ( i = 0 ; i < in.width ; i++ ) {
		for ( j = 0 ; j < in.height ; j++ ) {
			count = 0;
			dv = &in.verts[j*in.width+i];
			VectorCopy( dv->xyz, base );
			for ( k = 0 ; k < 8 ; k++ ) {
				VectorClear( around[k] );
				good[k] = qfalse;

				for ( dist = 1 ; dist <= 3 ; dist++ ) {
					x = i + neighbors[k][0] * dist;
					y = j + neighbors[k][1] * dist;
					if ( wrapWidth ) {
						if ( x < 0 ) {
							x = in.width - 1 + x;
						} else if ( x >= in.width ) {
							x = 1 + x - in.width;
						}
					}
					if ( wrapHeight ) {
						if ( y < 0 ) {
							y = in.height - 1 + y;
						} else if ( y >= in.height ) {
							y = 1 + y - in.height;
						}
					}

					if ( x < 0 || x >= in.width || y < 0 || y >= in.height ) {
						break;					// edge of patch
					}
					VectorSubtract( in.verts[y*in.width+x].xyz, base, temp );
					if ( VectorNormalize( temp, temp ) == 0 ) {
						continue;				// degenerate edge, get more dist
					} else {
						good[k] = qtrue;
						VectorCopy( temp, around[k] );
						break;					// good edge
					}
				}
			}

			VectorClear( sum );
			for ( k = 0 ; k < 8 ; k++ ) {
				if ( !good[k] || !good[(k+1)&7] ) {
					continue;	// didn't get two points
				}
				CrossProduct( around[(k+1)&7], around[k], normal );
				if ( VectorNormalize( normal, normal ) == 0 ) {
					continue;
				}
				VectorAdd( normal, sum, sum );
				count++;
			}
			if ( count == 0 ) {
//Sys_Printf("bad normal\n");
				count = 1;
			}
			VectorNormalize( sum, dv->normal );
		}
	}
}

/*
PutMeshOnCurve()
drops the aproximating points onto the curve
ydnar: fixme: make this use LerpDrawVert() rather than this complicated mess
*/

void PutMeshOnCurve( mesh_t in ) {
	int		i, j, l, m;
	float	prev, next;
	
	
	// put all the aproximating points on the curve
	for ( i = 0 ; i < in.width ; i++ ) {
		for ( j = 1 ; j < in.height ; j += 2 ) {
			for ( l = 0 ; l < 3 ; l++ ) {
				prev = ( in.verts[j*in.width+i].xyz[l] + in.verts[(j+1)*in.width+i].xyz[l] ) * 0.5;
				next = ( in.verts[j*in.width+i].xyz[l] + in.verts[(j-1)*in.width+i].xyz[l] ) * 0.5;
				in.verts[j*in.width+i].xyz[l] = ( prev + next ) * 0.5;
				
				/* ydnar: interpolating st coords */
				if( l < 2 )
				{
					prev = ( in.verts[j*in.width+i].st[l] + in.verts[(j+1)*in.width+i].st[l] ) * 0.5;
					next = ( in.verts[j*in.width+i].st[l] + in.verts[(j-1)*in.width+i].st[l] ) * 0.5;
					in.verts[j*in.width+i].st[l] = ( prev + next ) * 0.5;
					
					for( m = 0; m < MAX_LIGHTMAPS; m++ )
					{
						prev = ( in.verts[j*in.width+i].lightmap[ m ][l] + in.verts[(j+1)*in.width+i].lightmap[ m ][l] ) * 0.5;
						next = ( in.verts[j*in.width+i].lightmap[ m ][l] + in.verts[(j-1)*in.width+i].lightmap[ m ][l] ) * 0.5;
						in.verts[j*in.width+i].lightmap[ m ][l] = ( prev + next ) * 0.5;
					}
				}
			}
		}
	}
	
	for ( j = 0 ; j < in.height ; j++ ) {
		for ( i = 1 ; i < in.width ; i += 2 ) {
			for ( l = 0 ; l < 3 ; l++ ) {
				prev = ( in.verts[j*in.width+i].xyz[l] + in.verts[j*in.width+i+1].xyz[l] ) * 0.5;
				next = ( in.verts[j*in.width+i].xyz[l] + in.verts[j*in.width+i-1].xyz[l] ) * 0.5;
				in.verts[j*in.width+i].xyz[l] = ( prev + next ) * 0.5;
				
				/* ydnar: interpolating st coords */
				if( l < 2 )
				{
					prev = ( in.verts[j*in.width+i].st[l] + in.verts[j*in.width+i+1].st[l] ) * 0.5;
					next = ( in.verts[j*in.width+i].st[l] + in.verts[j*in.width+i-1].st[l] ) * 0.5;
					in.verts[j*in.width+i].st[l] = ( prev + next ) * 0.5;
					
					for( m = 0; m < MAX_LIGHTMAPS; m++ )
					{
						prev = ( in.verts[j*in.width+i].lightmap[ m ][l] + in.verts[j*in.width+i+1].lightmap[ m ][l] ) * 0.5;
						next = ( in.verts[j*in.width+i].lightmap[ m ][l] + in.verts[j*in.width+i-1].lightmap[ m ][l] ) * 0.5;
						in.verts[j*in.width+i].lightmap[ m ][l] = ( prev + next ) * 0.5;
					}
				}
			}
		}
	}
}


/*
=================
SubdivideMesh

=================
*/
mesh_t *SubdivideMesh( mesh_t in, float maxError, float minLength )
{
	int							i, j, k, l;
	bspDrawVert_t				prev, next, mid;
	vec3_t						prevxyz, nextxyz, midxyz;
	vec3_t						delta;
	float						len;
	mesh_t						out;
	
	/* ydnar: static for os x */
	MAC_STATIC bspDrawVert_t	expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS];
	
	
	out.width = in.width;
	out.height = in.height;

	for ( i = 0 ; i < in.width ; i++ ) {
		for ( j = 0 ; j < in.height ; j++ ) {
			expand[j][i] = in.verts[j*in.width+i];
		}
	}

	// horizontal subdivisions
	for ( j = 0 ; j + 2 < out.width ; j += 2 ) {
		// check subdivided midpoints against control points
		for ( i = 0 ; i < out.height ; i++ ) {
			for ( l = 0 ; l < 3 ; l++ ) {
				prevxyz[l] = expand[i][j+1].xyz[l] - expand[i][j].xyz[l]; 
				nextxyz[l] = expand[i][j+2].xyz[l] - expand[i][j+1].xyz[l]; 
				midxyz[l] = (expand[i][j].xyz[l] + expand[i][j+1].xyz[l] * 2
						+ expand[i][j+2].xyz[l] ) * 0.25;
			}

			// if the span length is too long, force a subdivision
			if ( VectorLength( prevxyz ) > minLength 
				|| VectorLength( nextxyz ) > minLength ) {
				break;
			}

			// see if this midpoint is off far enough to subdivide
			VectorSubtract( expand[i][j+1].xyz, midxyz, delta );
			len = VectorLength( delta );
			if ( len > maxError ) {
				break;
			}
		}

		if ( out.width + 2 >= MAX_EXPANDED_AXIS ) {
			break;	// can't subdivide any more
		}

		if ( i == out.height ) {
			continue;	// didn't need subdivision
		}

		// insert two columns and replace the peak
		out.width += 2;

		for ( i = 0 ; i < out.height ; i++ ) {
			LerpDrawVert( &expand[i][j], &expand[i][j+1], &prev );
			LerpDrawVert( &expand[i][j+1], &expand[i][j+2], &next );
			LerpDrawVert( &prev, &next, &mid );

			for ( k = out.width - 1 ; k > j + 3 ; k-- ) {
				expand[i][k] = expand[i][k-2];
			}
			expand[i][j + 1] = prev;
			expand[i][j + 2] = mid;
			expand[i][j + 3] = next;
		}

		// back up and recheck this set again, it may need more subdivision
		j -= 2;

	}

	// vertical subdivisions
	for ( j = 0 ; j + 2 < out.height ; j += 2 ) {
		// check subdivided midpoints against control points
		for ( i = 0 ; i < out.width ; i++ ) {
			for ( l = 0 ; l < 3 ; l++ ) {
				prevxyz[l] = expand[j+1][i].xyz[l] - expand[j][i].xyz[l]; 
				nextxyz[l] = expand[j+2][i].xyz[l] - expand[j+1][i].xyz[l]; 
				midxyz[l] = (expand[j][i].xyz[l] + expand[j+1][i].xyz[l] * 2
						+ expand[j+2][i].xyz[l] ) * 0.25;
			}

			// if the span length is too long, force a subdivision
			if ( VectorLength( prevxyz ) > minLength 
				|| VectorLength( nextxyz ) > minLength ) {
				break;
			}
			// see if this midpoint is off far enough to subdivide
			VectorSubtract( expand[j+1][i].xyz, midxyz, delta );
			len = VectorLength( delta );
			if ( len > maxError ) {
				break;
			}
		}

		if ( out.height + 2 >= MAX_EXPANDED_AXIS ) {
			break;	// can't subdivide any more
		}

		if ( i == out.width ) {
			continue;	// didn't need subdivision
		}

		// insert two columns and replace the peak
		out.height += 2;

		for ( i = 0 ; i < out.width ; i++ ) {
			LerpDrawVert( &expand[j][i], &expand[j+1][i], &prev );
			LerpDrawVert( &expand[j+1][i], &expand[j+2][i], &next );
			LerpDrawVert( &prev, &next, &mid );

			for ( k = out.height - 1 ; k > j + 3 ; k-- ) {
				expand[k][i] = expand[k-2][i];
			}
			expand[j+1][i] = prev;
			expand[j+2][i] = mid;
			expand[j+3][i] = next;
		}

		// back up and recheck this set again, it may need more subdivision
		j -= 2;

	}

	// collapse the verts

	out.verts = &expand[0][0];
	for ( i = 1 ; i < out.height ; i++ ) {
		memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(bspDrawVert_t) );
	}

	return CopyMesh(&out);
}



/*
IterationsForCurve() - ydnar
given a curve of a certain length, return the number of subdivision iterations
note: this is affected by subdivision amount
*/

int IterationsForCurve( float len, int subdivisions )
{
	int		iterations, facets;
	
	
	/* calculate the number of subdivisions */
	for( iterations = 0; iterations < 3; iterations++ )
	{
		facets = subdivisions * 16 * pow( 2, iterations );
		if( facets >= len )
			break;
	}
	
	/* return to caller */
	return iterations;
}


/*
SubdivideMesh2() - ydnar
subdivides each mesh quad a specified number of times
*/

mesh_t *SubdivideMesh2( mesh_t in, int iterations )
{
	int							i, j, k;
	bspDrawVert_t				prev, next, mid;
	mesh_t						out;
	
	/* ydnar: static for os x */
	MAC_STATIC bspDrawVert_t	expand[ MAX_EXPANDED_AXIS ][ MAX_EXPANDED_AXIS ];
	
	
	/* initial setup */
	out.width = in.width;
	out.height = in.height;
	for( i = 0; i < in.width; i++ )
	{
		for( j = 0; j < in.height; j++ )
			expand[ j ][ i ] = in.verts[ j * in.width + i ];
	}
	
	/* keep chopping */
	for( ; iterations > 0; iterations-- )
	{
		/* horizontal subdivisions */
		for( j = 0; j + 2 < out.width; j += 4 )
		{
			/* check size limit */
			if( out.width + 2 >= MAX_EXPANDED_AXIS )
				break;
			
			/* insert two columns and replace the peak */
			out.width += 2;
			for( i = 0; i < out.height; i++ )
			{
				LerpDrawVert( &expand[ i ][ j ], &expand[ i ][ j + 1 ], &prev );
				LerpDrawVert( &expand[ i ][ j + 1 ], &expand[ i ][ j + 2 ], &next );
				LerpDrawVert( &prev, &next, &mid );

				for ( k = out.width - 1 ; k > j + 3; k-- )
					expand [ i ][ k ] = expand[ i ][ k - 2 ];
				expand[ i ][ j + 1 ] = prev;
				expand[ i ][ j + 2 ] = mid;
				expand[ i ][ j + 3 ] = next;
			}
			
		}

		/* vertical subdivisions */
		for ( j = 0; j + 2 < out.height; j += 4 )
		{
			/* check size limit */
			if( out.height + 2 >= MAX_EXPANDED_AXIS )
				break;
			
			/* insert two columns and replace the peak */
			out.height += 2;
			for( i = 0; i < out.width; i++ )
			{
				LerpDrawVert( &expand[ j ][ i ], &expand[ j + 1 ][ i ], &prev );
				LerpDrawVert( &expand[ j + 1 ][ i ], &expand[ j + 2 ][ i ], &next );
				LerpDrawVert( &prev, &next, &mid );
				
				for( k = out.height - 1; k > j  +  3; k-- )
					expand[ k ][ i ] = expand[ k - 2 ][ i ];
				expand[ j + 1 ][ i ] = prev;
				expand[ j + 2 ][ i ] = mid;
				expand[ j + 3 ][ i ] = next;
			}
		}
	}
	
	/* collapse the verts */
	out.verts = &expand[ 0 ][ 0 ];
	for( i = 1; i < out.height; i++ )
		memmove( &out.verts[ i * out.width ], expand[ i ], out.width * sizeof( bspDrawVert_t ) );
	
	/* return to sender */
	return CopyMesh( &out );
}







/*
================
ProjectPointOntoVector
================
*/
void ProjectPointOntoVector( vec3_t point, vec3_t vStart, vec3_t vEnd, vec3_t vProj )
{
	vec3_t pVec, vec;

	VectorSubtract( point, vStart, pVec );
	VectorSubtract( vEnd, vStart, vec );
	VectorNormalize( vec, vec );
	// project onto the directional vector for this segment
	VectorMA( vStart, DotProduct( pVec, vec ), vec, vProj );
}

/*
================
RemoveLinearMeshColumsRows
================
*/
mesh_t *RemoveLinearMeshColumnsRows( mesh_t *in ) {
	int							i, j, k;
	float						len, maxLength;
	vec3_t						proj, dir;
	mesh_t						out;
	
	/* ydnar: static for os x */
	MAC_STATIC bspDrawVert_t	expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS];
	

	out.width = in->width;
	out.height = in->height;

	for ( i = 0 ; i < in->width ; i++ ) {
		for ( j = 0 ; j < in->height ; j++ ) {
			expand[j][i] = in->verts[j*in->width+i];
		}
	}

	for ( j = 1 ; j < out.width - 1; j++ ) {
		maxLength = 0;
		for ( i = 0 ; i < out.height ; i++ ) {
			ProjectPointOntoVector(expand[i][j].xyz, expand[i][j-1].xyz, expand[i][j+1].xyz, proj);
			VectorSubtract(expand[i][j].xyz, proj, dir);
			len = VectorLength(dir);
			if (len > maxLength) {
				maxLength = len;
			}
		}
		if (maxLength < 0.1)
		{
			out.width--;
			for ( i = 0 ; i < out.height ; i++ ) {
				for (k = j; k < out.width; k++) {
					expand[i][k] = expand[i][k+1];
				}
			}
			j--;
		}
	}
	for ( j = 1 ; j < out.height - 1; j++ ) {
		maxLength = 0;
		for ( i = 0 ; i < out.width ; i++ ) {
			ProjectPointOntoVector(expand[j][i].xyz, expand[j-1][i].xyz, expand[j+1][i].xyz, proj);
			VectorSubtract(expand[j][i].xyz, proj, dir);
			len = VectorLength(dir);
			if (len > maxLength) {
				maxLength = len;
			}
		}
		if (maxLength < 0.1)
		{
			out.height--;
			for ( i = 0 ; i < out.width ; i++ ) {
				for (k = j; k < out.height; k++) {
					expand[k][i] = expand[k+1][i];
				}
			}
			j--;
		}
	}
	// collapse the verts
	out.verts = &expand[0][0];
	for ( i = 1 ; i < out.height ; i++ ) {
		memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(bspDrawVert_t) );
	}

	return CopyMesh(&out);
}



/*
=================
SubdivideMeshQuads
=================
*/
mesh_t *SubdivideMeshQuads( mesh_t *in, float minLength, int maxsize, int *widthtable, int *heighttable )
{
	int				i, j, k, w, h, maxsubdivisions, subdivisions;
	vec3_t			dir;
	float			length, maxLength, amount;
	mesh_t			out;
	bspDrawVert_t	expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS];

	out.width = in->width;
	out.height = in->height;

	for ( i = 0 ; i < in->width ; i++ ) {
		for ( j = 0 ; j < in->height ; j++ ) {
			expand[j][i] = in->verts[j*in->width+i];
		}
	}

	if (maxsize > MAX_EXPANDED_AXIS)
		Error("SubdivideMeshQuads: maxsize > MAX_EXPANDED_AXIS");

	// horizontal subdivisions

	maxsubdivisions = (maxsize - in->width) / (in->width - 1);

	for ( w = 0, j = 0 ; w < in->width - 1; w++, j += subdivisions + 1) {
		maxLength = 0;
		for ( i = 0 ; i < out.height ; i++ ) {
			VectorSubtract(expand[i][j+1].xyz, expand[i][j].xyz, dir);
			length = VectorLength( dir );
			if (length > maxLength) {
				maxLength = length;
			}
		}
		
		subdivisions = (int) (maxLength / minLength);
		if (subdivisions > maxsubdivisions)
			subdivisions = maxsubdivisions;

		widthtable[w] = subdivisions + 1;
		if (subdivisions <= 0)
			continue;

		out.width += subdivisions;

		for ( i = 0 ; i < out.height ; i++ ) {
			for ( k = out.width - 1 ; k > j + subdivisions; k-- ) {
				expand[i][k] = expand[i][k-subdivisions];
			}
			for (k = 1; k <= subdivisions; k++)
			{
				amount = (float) k / (subdivisions + 1);
				LerpDrawVertAmount(&expand[i][j], &expand[i][j+subdivisions+1], amount, &expand[i][j+k]);
			}
		}
	}

	maxsubdivisions = (maxsize - in->height) / (in->height - 1);

	for ( h = 0, j = 0 ; h < in->height - 1; h++, j += subdivisions + 1) {
		maxLength = 0;
		for ( i = 0 ; i < out.width ; i++ ) {
			VectorSubtract(expand[j+1][i].xyz, expand[j][i].xyz, dir);
			length = VectorLength( dir );
			if (length  > maxLength) {
				maxLength = length;
			}
		}
		
		subdivisions = (int) (maxLength / minLength);
		if (subdivisions > maxsubdivisions)
			subdivisions = maxsubdivisions;

		heighttable[h] = subdivisions + 1;
		if (subdivisions <= 0)
			continue;

		out.height += subdivisions;

		for ( i = 0 ; i < out.width ; i++ ) {
			for ( k = out.height - 1 ; k > j + subdivisions; k-- ) {
				expand[k][i] = expand[k-subdivisions][i];
			}
			for (k = 1; k <= subdivisions; k++)
			{
				amount = (float) k / (subdivisions + 1);
				LerpDrawVertAmount(&expand[j][i], &expand[j+subdivisions+1][i], amount, &expand[j+k][i]);
			}
		}
	}

	// collapse the verts
	out.verts = &expand[0][0];
	for ( i = 1 ; i < out.height ; i++ ) {
		memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(bspDrawVert_t) );
	}

	return CopyMesh(&out);
}
